package solution;

class Solution1 {
    /**
     *931. 下降路径最小和
     * https://leetcode.cn/problems/minimum-falling-path-sum/description/
     * @param matrix
     * @return
     */
    public int minFallingPathSum(int[][] matrix) {
        //1、建立dp表
        int n = matrix.length;//方形的，不用分别求行和列了
        int[][] dp = new int[n + 1][n + 2];
        //2、初始化dp表
        for(int i = 1; i < n + 1; i++) {
            //dp的第一列和最后一列赋值整型的最大值
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }
        //3、填表
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                //左上，上，右上的最小值 + 此时原表的值
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        //4、返回值
        int min = dp[n][0];
        for(int i = 1; i < n + 1; i++) {
            //找出最后一行（第n行）的最小值，返回这个最小值
            min = Math.min(min, dp[n][i]);
        }
        return min;
    }
}